package class07


/*
	在一个字符串中找到没有重复字符串子串中最长的长度
	例如：
		"abcabcbb" 没有重复字符串的最长子串是 abc，长度为3
		"bbbbbbb"  答案是b，长度为1
		"pwwkew"   答案是wke，长度是3
	要求：答案必须是子串，"pwke" 是一个子字符串序列但不是一个子字符串

	解法一：
		1. 使用map对字符做一个集合，将收集过字符进行记录
		2. 使用双指针获取范围内的字符串

*/
func MaxUnique(s string) int {
	var ans int
	if len(s) == 0 {
		return ans
	}
	BSet := make(map[byte]int)
	var pre, after int
	for i:=0; i<len(s); i++ {
		for n, ok := BSet[s[i]]; ok && n == 1 && pre <len(s) ; {
			BSet[s[pre]]--
			if BSet[s[pre]] == 0 {
				delete(BSet, s[pre])
			}
			pre++
		}
		BSet[s[after]] = 1
		after++
		ans = max(len(BSet), ans)
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/*
	使用动态规划的解法：
	假设dp[i]，的含义为以 s[i] 为结尾的字符串的最大不重复子串长度
	所以，针对每一个 i 位置有如下可能性：
		1) 最近一次出现与当前位置的字符相同的位置
		2) 以i-1为结尾的字符串上次可拓展到的起始位置
		如图：
				a		 a
			[..........] i
			    i-1 len
			如果重复字符出现在 i-1 之内，答案为上一个a到当前a的区间长度
			如果重复字符出现在 i-1 之外，上一个字符串的答案就是当前区间的答案
*/

func MaxUniqueDpWay(s string) int {
	if len(s) == 0 {
		return 0
	}
	dp := make([]int, len(s))
	recent := make([]int, 26)
	for i:=0; i<len(recent); i++ {
		recent[i] = -1
	}
	var ans int
	dp[0] = 1
	recent[s[0]-'a'] = 0 // 记录已经解析过字符的位置
	for i:=1; i<len(s); i++ {
		if recent[s[i] - 'a'] == -1 {
			dp[i] = dp[i-1] + 1
		} else {
			// a  e  c  c    e
			// 0  1  2  3    4
			//          i-1  i
			sameIndex := recent[s[i] - 'a']
			preIndex  := i + dp[i-1] - 2
			dp[i] = i - min(sameIndex, preIndex)
		}
		recent[s[i] - 'a'] = i
		ans = max(dp[i], ans)
	}
	return ans
}

